package io.github.consoles.dsa;

import java.util.Iterator;

/**
 * Created by yiihua-013 on 17/2/7.
 * <p>
 * 链表
 */
public class LinkedList<Item> implements Iterable<Item> {

    private class LinkedIterator implements Iterator<Item> {

        Node current = first;

        @Override
        public boolean hasNext() {
            return current != null;
        }

        @Override
        public Item next() {
            Item item = current.item;
            current = current.next;
            return item;
        }
    }

    @Override
    public Iterator<Item> iterator() {
        return new LinkedIterator();
    }

    public class Node implements Cloneable {
        Item item;
        Node next;

        Node(Item item) {
            this.item = item;
        }

        @Override
        protected Object clone() throws CloneNotSupportedException {
            return super.clone();
        }
    }

    /**
     * just for test convenient
     *
     * @param item
     * @return
     */
    public Node createNode(Item item) {
        return new Node(item);
    }

    private Node first; // 头结点
    private Node last; // 尾节点
    private int  size;

    public boolean isEmpty() {
        return first == null;
    }

    public int size() {
        return size;
    }

    /**
     * 删除链表的第k个元素
     *
     * @param k
     * @return
     */
    public void delete(int k) {
        if (k < 1) return;
        int count = 0;
        Node prev = null,
                current = first;

        // prev为k-1个节点,current为第k个节点
        while (++count < k && current != null) {
            prev = current;
            current = current.next;
        }
        if (current != null) {
            if (prev == null) first = current.next;  // 移除头结点
            else prev.next = current.next;
            if (current.next == null) last = prev;
            size--;
        }
    }

    public boolean find(Item item) {
        Node current = first;
        // 找到相等的就结束循环,此时current不为空
        while (current != null && !current.item.equals(item))
            current = current.next;
        return current != null;
    }

    public Node search(Item item) {
        Node current = first;
        while (current != null && !current.item.equals(item)) current = current.next;
        return current;
    }

    public void append(Item item) {
        Node node = new Node(item);
        if (isEmpty()) {
            first = node;
            last = node;
        } else {
            last.next = node;
            last = node;
            // 上面的2句和下面的等效
//            Node oldLast = last;
//            oldLast.next = node;
//            last = node;
        }
        size++;
    }

    /**
     * 删除该节点的所有后续节点
     *
     * @param node
     */
    public void removeAfter(Node node) {

        // 迭代断开每个节点
//        if (node != null && node.next != null) {
//            last = node;
//            Node current = node.next;
//            Node next = current.next;
//            node.next = null;
//            size--;
//            while (current.next != null) {
//                current = next;
//                next = next.next;
//                size--;
//            }
//        }

        // 断开将last设置为node并断开node.next,其余的交给gc,但是此时的size需要用另一种方式计算
        if (node != null && node.next != null) {
            last = node;
            node.next = null;
            int  count   = 0;
            Node current = first;
            while (current != null) {
                count++;
                current = current.next;
            }
            size = count;
        }
    }

    /**
     * 在a节点后插入b节点
     *
     * @param a
     * @param b
     */
    public void insertAfter(Node a, Node b) {
        if (a != null && b != null) {
            if (last == a) last = b;
            b.next = a.next;
            a.next = b;
            size++;

            // 上面的代码和下面的等效
//            Node oldANext = a.next;
//            a.next = b;
//            b.next = oldANext;
        }
    }

    /**
     * 移除链表中所有item域为item的元素
     *
     * @param item
     */
    public void remove(Item item) {
        int count = 1;
        // 以此调用delete移除链表中的元素
        Node current = first;
        while (current != null) {
            if (current.item.equals(item)) {
                delete(count);
                count--; // 删除一个元素之后原先链表元素少1,索引发生变化了
            }
            current = current.next;
            count++;
        }
    }

    public Item max() {

        Node current = first;
        Item max     = first.item;
        while (current.next != null) {
            current = current.next;
            if (((Comparable) max).compareTo(current.item) < 0) max = current.item;
        }
        return max;
    }

    public Node first() {
        return first;
    }

    /**
     * 递归的形式实现上面的max方法
     *
     * @return
     */
    public Item max(Node first) {

        if (first == null) return null;
        if (first.next == null) return first.item;

        Item max = max(first.next);

        return ((Comparable) first.item).compareTo(max) > 0 ? first.item : max;
    }

    /**
     * 破坏性将链表翻转并得到首节点
     *
     * @return
     */
    public Node reverse() {
        // 迭代方式:记录链表中三个连续的节点:reverse,first,second。
        // 在每轮迭代中,我们从原链表中提取节点first并将其插入到逆链表的开头。
        // 我们需要一直保持
        // first指向原链表中所有剩余节点的首节点,
        // second 指向原链表中所有剩余节点的第二个节点,
        // reverse指向结果链表的首节点
        Node reverse = null;
        while (first != null) {
            Node second = first.next;
            first.next = reverse;
            reverse = first;
            first = second;
        }
        return reverse;
    }

    /**
     * 递归实现破坏性的链表颠倒
     *
     * @param first
     * @return 假设链表含有N个节点, 先递归颠倒N-1个节点,然后小心将原链表的首节点插入到结果链表的末端
     */
    public Node reverse(Node first) {
        if (first == null) return null;
        if (first.next == null) return first;
        Node second = first.next;
        Node rest   = reverse(second);
        second.next = first;
        first.next = null;
        return rest;
    }

    public void insertBeforeFirst(Node node) {
        node.next = first;
        first = node;
    }
}
